// 二分搜索树

import { Node } from './model'

class BST {
  /**
   *
   * @param compare 比较器，接收参数为当前node和新的element
   */
  constructor (compare = (node, elem) => node.element - elem) {
    this.root = null
    this.size = 0 // 元素(结点)个数
    this.compare = compare
  }

  add (element) {
    const self = this
    // 私有的递归add过程， 返回当前二分搜索树的根结点(因为可以把任意的左子树或右子树看做一棵新的BST)
    function _add (node, element, self) {
      if (node === null) {
        self.size++
        return new Node(element)
      }
      if (self.compare(node, element) > 0) {
        // 当前结点比新结点大
        node.left = _add(node.left, element, self)
      } else if (self.compare(node, element) < 0) {
        node.right = _add(node.right, element, self)
      }
      return node
    }
    this.root = _add(this.root, element, self)
  }

  // 是否包含元素，查找
  contains (element) {
    const self = this
    // 查看以node为根节点的BST是否包含元素e
    function _contains (node, element, self) {
      if (node === null) {
        return false
      }
      if (self.compare(node, element) === 0) {
        return true // 已经找到
      } else if (self.compare(node, element) < 0) {
        // 如果当前结点<目标，找右子树
        return _contains(node.right, element, self)
      } else {
        // 当前结点>目标，找左子树
        return _contains(node.left, element, self)
      }
    }
    return _contains(this.root, element, self)
  }

  // 前序遍历  me->left->right
  preOrder () {
    function _preOrder (node) {
      if (node === null) {
        return
      }
      console.log(node.element)
      _preOrder(node.left)
      _preOrder(node.right)
    }
    _preOrder(this.root)
  }

  /* 前序遍历 非递归写法
    思路: 遇到节点先压栈,然后弹栈,访问元素,压入right,left;访问元素...
   */
  preOrderNoRecursive () {
    const stack = [] // js 数组模拟栈
    stack.push(this.root)
    let node
    while (stack.length) {
      node = stack.pop()
      if (node !== null) {
        console.log(node.element)
      }
      if (node.right !== null) {
        stack.push(node.right)
      }
      if (node.right !== null) {
        stack.push(node.left)
      }
    }
  }

  // 中序遍历 left->me->right: 二分搜索树的性质：中序遍历就是排序后的结果
  inOrder () {
    function _inOrder (node) {
      if (node === null) {
        return
      }
      _inOrder(node.left)
      console.log(node.element)
      _inOrder(node.right)
    }
    _inOrder(this.root)
  }

  // 后序遍历 left->right->me
  postOrder () {
    function _postOrder (node) {
      if (node === null) {
        return
      }
      _postOrder(node.left)
      _postOrder(node.right)
      console.log(node.element)
    }
    _postOrder(this.root)
  }

  // 层级遍历(广度优先便利), 思路: 使用队列, 将节点入队，出队节点打印，其左右子树入队，再出队...
  levelOrder () {
    const queue = [] // 模拟一个队列
    queue.push(this.root)
    let node
    while (queue.length) {
      node = queue.shift() // 出队
      if (node !== null) {
        console.log(node.element)
      }
      if (node.left !== null) {
        queue.push(node.left)
      }
      if (node.right !== null) {
        queue.push(node.right)
      }
    }
  }

  // 找到最小值
  getMin () {
    return this._getMin(this.root).element
  }

  _getMin (node) {
    if (node.left === null) {
      return node
    }
    return this._getMin(node.left)
  }

  // 找到最大值
  getMax () {
    return this._getMax(this.root).element
  }

  _getMax (node) {
    if (node.right === null) {
      return node
    }
    return this._getMin(node.right)
  }

  // 删除最小值
  removeMin () {
    const min = this.getMin()
    this.root = this._removeMin(this.root)
    this.size--
    return min
  }

  // 返回以node为根的BST，删除最小值之后的根节点
  _removeMin (node) {
    if (node.left === null) {
      // 此时node即为要删除的Min节点
      const rightNode = node.right // 保存其右结点
      node.right = null // 解绑node的右节点
      return rightNode
    }
    node.left = this._removeMin(node.left)
    return node
  }

  // 删除最大值
  removeMax () {
    const max = this.getMax()
    this.root = this._removeMax(this.root)
    this.size--
    return max
  }

  _removeMax (node) {
    if (node.right === null) {
      // 此时node即为要删除的Max节点
      const leftNode = node.left // 保存其左结点
      node.left = null // 解绑node的左节点
      return leftNode
    }
    node.right = this._removeMin(node.right)
    return node
  }

  // 删除任意节点
  remove (element) {
    this.root = this._remove(this.root, element)
  }

  _remove (node, element) {
    if (node === null) {
      return null
    }
    if (this.compare(node, element) < 0) {
      // node < element
      node.right = this._remove(node.right, element)
      return node
    } else if (this.compare(node, element) > 0) {
      // node > element
      node.left = this._remove(node.left, element)
      return node
    } else {
      // node === element
      if (node.left === null) {
        // node没有left
        const rightNode = node.right // 保存其右结点
        node.right = null // 解绑node的右节点
        this.size--
        return rightNode
      } else if (node.right === null) {
        const leftNode = node.left // 保存其左结点
        node.left = null // 解绑node的左节点
        this.size--
        return leftNode
      } else {
        // 左右子树均存在
        /*
        思路: 找到比当前删除节点大的最小节点(删除节点的右子树最小值),用这个最小节点代替删除节点(
         */
        const successor = this._getMin(node.right)
        successor.right = this._removeMin(node.right) // 最小节点取出，接替node的右子树, removeMin已经将size--
        successor.left = node.left

        node.left = node.right = null // 解绑要删除的节点
        return successor // 返回根节点
      }
    }
  }
}

export default BST
